package com.Dec_Twentytwo;

/**
 * 878. 第 N 个神奇数字
 * 一个正整数如果能被 a 或 b 整除，那么它是神奇的。
 *
 * 给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/nth-magical-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/11/22 11:30
 */

public class Solution878 {

    int n,a,b,c;

    int gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }

    public int nthMagicalNumber(int _n, int _a, int _b) {
        n=_n;a=_a;b=_b;c=a*b/gcd(a,b);
        long l=0,r=(long) 1e20;
        while (l<r){
            long mid=l+r>>1;
            if (check(mid)>=n) r=mid;
            else l=mid+1;
        }
        return (int) (r%1000000007);
    }

    long check(long x){
        return x/a+x/b-x/c;
    }

    public static void main(String[] args) {
        Solution878 solution878=new Solution878();
        System.out.println(solution878.nthMagicalNumber(4,2,3));
    }
}
